package leetcode.editor.cn;//给你一个链表数组，每个链表都已经按升序排列。
//
// 请你将所有链表合并到一个升序链表中，返回合并后的链表。 
//
// 
//
// 示例 1： 
//
// 输入：lists = [[1,4,5],[1,3,4],[2,6]]
//输出：[1,1,2,3,4,4,5,6]
//解释：链表数组如下：
//[
//  1->4->5,
//  1->3->4,
//  2->6
//]
//将它们合并到一个有序链表中得到。
//1->1->2->3->4->4->5->6
// 
//
// 示例 2： 
//
// 输入：lists = []
//输出：[]
// 
//
// 示例 3： 
//
// 输入：lists = [[]]
//输出：[]
// 
//
// 
//
// 提示： 
//
// 
// k == lists.length 
// 0 <= k <= 10^4 
// 0 <= lists[i].length <= 500 
// -10^4 <= lists[i][j] <= 10^4 
// lists[i] 按 升序 排列 
// lists[i].length 的总和不超过 10^4 
// 
// Related Topics 链表 分治 堆（优先队列） 归并排序 
// 👍 1746 👎 0


//leetcode submit region begin(Prohibit modification and deletion)

import java.util.PriorityQueue;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution23 {


    class HeapNode implements Comparable<HeapNode> {
        int val;
        ListNode ptr;

        HeapNode(int val, ListNode ptr) {
            this.val = val;
            this.ptr = ptr;
        }

        public int compareTo(HeapNode heapNode2) {
            return this.val - heapNode2.val;
        }
    }


    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<HeapNode> heap=new PriorityQueue<>();
        //将所有链表头结点加入堆
        for(ListNode head:lists){
            if(head!=null)
                heap.offer(new HeapNode(head.val,head));
        }
        ListNode dummy=new ListNode(0),p=dummy;
        while(heap.size()>0){
            p.next=heap.poll().ptr;
            p=p.next;
            if(p.next!=null)
                heap.offer(new HeapNode(p.next.val,p.next));
        }
        return dummy.next;

    }
    public ListNode mergeList(ListNode head1, ListNode head2) {
        if (head2 == null)
            return head1;
        if (head1 == null)
            return head2;
        ListNode dummy = new ListNode(0);
        ListNode p = dummy;
        while (head1 != null && head2 != null) {
            if (head1.val > head2.val) {
                p.next =head2;
                head2=head2.next;
            }
            else {
                p.next =head1;
                head1=head1.next;
            }
            p=p.next;
        }
        if(head1==null) p.next=head2;
        else p.next=head1;
        return dummy.next;


    }

    public ListNode mergeList00(ListNode head1, ListNode head2) {
        if (head2 == null)
            return head1;
        if (head1 == null) return head2;
        if (head1.val > head2.val) {
            head2.next = mergeList(head1, head2.next);
            return head2;
        }
        head1.next = mergeList(head1.next, head2);
        return head1;


    }

    public ListNode mergeKLists00(ListNode[] lists) {
        if(lists.length<=0) return null;
        int len = lists.length, i;
        int interval = 1;//两两合并的链表间隔
        while (interval < len) {// 1 2 3 4 5 6
            for (i = 0; i + interval < len; i = i + 2*interval){

                lists[i] = mergeList(lists[i], lists[i + interval]);
            }
            interval*=2;

        }
        return lists[0];//[[1,4,5],[1,3,4],[2,6],[7],[8],[9]]
    }


}

//leetcode submit region end(Prohibit modification and deletion)
